【系列开头】开这个系列是因为最近学习某些算法纸上谈兵太久，算法流程背的再熟，没有实现过就没法真正的理解算法的细节。这个系列要实现算法的顺序为逻辑回归、决策树(CART)、AdaBoost、GBDT。其他算法根据后续学习情况进行添加。

本文的主要目的是贴出实现代码，并比较ID3、C4.5和CART三种决策树在实现分类与回归问题中的不同。

C4.5在ID3基础上继承并改进，主要涉及到以下几个方面的改进：

决策树的特征选择： 如果通过暴力枚举所有的可能的情况来选择损失最小的树结构是NP难问题，所以决策树采用的是一种贪心算法，每次尝试分裂一个叶节点，计算分裂前后的增益，选择增益最大的。 决策树的生成： 决策树的生成是一个递归的构建树的过程，其中ID3和C4.5构建的是多叉树，而CART构建的一定是二叉树。 决策树的剪枝： 决策树的剪枝是一个极小化损失函数的过程，这个损失函数包括预测误差和树的复杂度。在剪枝过程中，由于损失函数的计算可以在局部进行，因此考虑使用一种动态规划的算法进行实现。下面说一下CART算法的剪枝过程，其思想也是极小化损失函数，不同的是采用的一种递归的实现思路，将每一个内部节点的剪枝前后的损失函数减少值视为损失函数的参数α，每次剪枝最小的，得到一个α不同区间最优子树的序列，然后通过交叉验证计算子树序列的预测误差来选取最优子树，同时参数α也随之确定。

ID3算法采用信息增益、C4.5采用信息增益比、CART采用Gini系数。

CART算法是后来一种比较好的实现，但是在实现分类和回归两种方法的时候，代码几乎一样，可以说CART中的分类树就是回归树。

首先从分类和回归两种用途来看。 【ID3和C4.5】分类通过计算信息增益/信息增益比，递归的挑选信息增益最大的作为最优特征进行分裂；

【CART】分类和回归都是递归的选择一个特征进行二分，区别在于分类使用基尼系数来衡量一个特征下的类别纯度，并选取基尼指数高的；而回归是利用分裂某一特征左右两个区域的均方误差最小化准则来求解最优输出。

分类（自底向上代码）：